def is_bst(t):
    """Returns True if the Tree t has the structure of a valid BST."""
    if t is None:
        return True
    
    # 检查是否超过两个分支
    if len(t.branches) > 2:
        return False
    
    # 处理单分支情况
    if len(t.branches) == 1:
        child = t.branches[0]
        # 递归检查子树是否为BST
        if not is_bst(child):
            return False
        
        # 左子树情况：子树值 <= 当前节点值
        if child.label <= t.label:
            return bst_max(child) <= t.label
        # 右子树情况：子树值 >= 当前节点值
        elif child.label >= t.label:
            return bst_min(child) >= t.label
        
        return False
    
    # 处理双分支情况
    if len(t.branches) == 2:
        left, right = t.branches[0], t.branches[1]
        # 基本值检查
        if left.label > t.label or right.label < t.label:
            return False
        # 递归检查子树
        if not is_bst(left) or not is_bst(right):
            return False
        # 检查左右子树的最大最小值是否符合要求
        return bst_max(left) <= t.label and bst_min(right) >= t.label
    
    # 叶子节点是有效的BST
    return True

def bst_min(t):
    """返回BST中的最小值"""
    if t is None:
        return None
    
    if t.is_leaf():
        return t.label
    
    # 如果不是二叉树结构，返回None表示不是有效BST
    if len(t.branches) > 2:
        return None
    
    if len(t.branches) == 1:
        child = t.branches[0]
        # 右子树情况
        if child.label >= t.label:
            child_min = bst_min(child)
            return min(t.label, child_min) if child_min is not None else t.label
        # 左子树情况
        elif child.label <= t.label:
            child_min = bst_min(child)
            return child_min if child_min is not None else t.label
        else:
            return None
    
    # 双分支情况
    left, right = t.branches[0], t.branches[1]
    # 先检查基本结构是否有效
    if left.label > t.label or right.label < t.label:
        return None
    
    left_min = bst_min(left)
    right_min = bst_min(right)
    
    if left_min is None or right_min is None:
        return None
    
    return min(left_min, t.label, right_min)

def bst_max(t):
    """返回BST中的最大值"""
    if t is None:
        return None
    
    if t.is_leaf():
        return t.label
    
    # 如果不是二叉树结构，返回None表示不是有效BST
    if len(t.branches) > 2:
        return None
    
    if len(t.branches) == 1:
        child = t.branches[0]
        # 左子树情况
        if child.label <= t.label:
            child_max = bst_max(child)
            return max(t.label, child_max) if child_max is not None else t.label
        # 右子树情况
        elif child.label >= t.label:
            child_max = bst_max(child)
            return child_max if child_max is not None else t.label
        else:
            return None
        
    # 双分支情况
    left, right = t.branches[0], t.branches[1]
    # 先检查基本结构是否有效
    if left.label > t.label or right.label < t.label:
        return None
    
    left_max = bst_max(left)
    right_max = bst_max(right)
    
    if left_max is None or right_max is None:
        return None
    
    return max(left_max, t.label, right_max)

class Tree:
    """A tree has a label and a list of branches."""
    def __init__(self, label, branches=[]):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches
    
    def __repr__(self):
        """定义树的字符串表示形式，用于打印和测试"""
        if self.branches:
            return f"Tree({self.label}, {self.branches})"
        else:
            return f"Tree({self.label})"

def prune_small(t, n):
    """Prune the tree mutatively, keeping only the n branches
    of each node with the smallest labels.

    >>> t1 = Tree(6)
    >>> prune_small(t1, 2)
    >>> t1
    Tree(6)
    >>> t2 = Tree(6, [Tree(3), Tree(4)])
    >>> prune_small(t2, 1)
    >>> t2
    Tree(6, [Tree(3)])
    >>> t3 = Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2), Tree(3)]), Tree(5, [Tree(3), Tree(4)])])
    >>> prune_small(t3, 2)
    >>> t3
    Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])])
    """
    while len(t.branches) > n:
        largest = max(t.branches, key=lambda x : x.label)
        del t.branches[t.branches.index(largest)]
    for b in t.branches:
        prune_small(b, n)

class Link:
    """A linked list is either a Link object or Link.empty

    >>> s = Link(3, Link(4, Link(5)))
    >>> s.rest
    Link(4, Link(5))
    >>> s.rest.rest.rest is Link.empty
    True
    >>> s.rest.first * 2
    8
    >>> print(s)
    <3 4 5>
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '<'
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + '>'
    
def sum_rec(s, k):
    """Return the sum of the first k elements in s.

    >>> a = Link(1, Link(6, Link(8)))
    >>> sum_rec(a, 2)
    7
    >>> sum_rec(a, 5)
    15
    >>> sum_rec(Link.empty, 1)
    0
    """
    # Use a recursive call to sum_rec; don't call sum_iter
    "*** YOUR CODE HERE ***"
    if k == 0 or s is Link.empty:
        return 0
    return s.first + sum_rec(s.rest, k-1)

def sum_iter(s, k):
    """Return the sum of the first k elements in s.

    >>> a = Link(1, Link(6, Link(8)))
    >>> sum_iter(a, 2)
    7
    >>> sum_iter(a, 5)
    15
    >>> sum_iter(Link.empty, 1)
    0
    """
    # Don't call sum_rec or sum_iter
    "*** YOUR CODE HERE ***"
    t = s
    n = k
    sum = 0
    while n > 0 and t is not Link.empty:
        sum += t.first
        n -= 1
        t = t.rest
    return sum

def overlap(s, t):
    """For increasing s and t, count the numbers that appear in both.

    >>> a = Link(3, Link(4, Link(6, Link(7, Link(9, Link(10))))))
    >>> b = Link(1, Link(3, Link(5, Link(7, Link(8)))))
    >>> overlap(a, b)  # 3 and 7
    2
    >>> overlap(a.rest, b)  # just 7
    1
    >>> overlap(Link(0, a), Link(0, b))
    3
    """
    "*** YOUR CODE HERE ***"
    if s is Link.empty or t is Link.empty:
        return 0
    
    if s.first == t.first:
        return 1 + overlap(s.rest, t.rest)
    elif s.first < t.first:
        return overlap(s.rest, t)
    else:
        return overlap(t.rest, s)

def overlap_iter(s, t):
    """For increasing s and t, count the numbers that appear in both.

    >>> a = Link(3, Link(4, Link(6, Link(7, Link(9, Link(10))))))
    >>> b = Link(1, Link(3, Link(5, Link(7, Link(8)))))
    >>> overlap(a, b)  # 3 and 7
    2
    >>> overlap(a.rest, b)  # just 7
    1
    >>> overlap(Link(0, a), Link(0, b))
    3
    """
    "*** YOUR CODE HERE ***"
    count = 0
    current_s = s
    current_t = t
    while current_s is not Link.empty and current_t is not Link.empty:
        if current_s.first == current_t.first:
            count += 1
            current_s = current_s.rest
            current_t = current_t.rest
        elif current_s.first < current_t.first:
            current_s = current_s.rest
        else:
            current_t = current_t.rest